package pl.poznan.put.cs.to.tsp.localsearch;

import java.util.List;
import java.util.Random;

import pl.poznan.put.cs.to.tsp.common.Vertexes;

public class VertexExchangeHandler implements IMoveHandler {
	private List<Integer> a;
	private List<Integer> b;
	private Vertexes vertexes;
	private Random random;
	private boolean improved;
	private TabuManager tabuManager;

	public VertexExchangeHandler(List<Integer> a, List<Integer> b,
			Vertexes vertexes, TabuManager tabuManager) {
		this.a = a;
		this.b = b;
		this.vertexes = vertexes;
		this.random = new Random();
		this.tabuManager = tabuManager;

		// System.out.println("BEFORE:");
		// System.out.println("A:");
		// this.printList(this.a);
		// System.out.println("B:");
		// this.printList(this.b);

		if (a.size() == 0 || b.size() == 0) {
			this.improved = false;
		} else {
			this.improved = this.tryVertexExchange();
		}

		// System.out.println();
		// System.out.println("AFTER:");
		// System.out.println("A:");
		// this.printList(this.a);
		// System.out.println("B:");
		// this.printList(this.b);
	}

	// private void printList(List<Integer> list) {
	// for (int i : list) {
	// System.out.print(i + " ");
	// }
	// // System.out.println();
	// // System.out.println("n = " + list.size());
	// }

	private boolean tryVertexExchange() {
		boolean better = false;

		int firstIndexA = this.random.nextInt(this.a.size());
		int firstIndexB = this.random.nextInt(this.b.size());

		int actualIndexA = firstIndexA;
		int actualIndexB = firstIndexB;

		int tabuA = -1;
		int tabuB = -1;
		int tabuExchangeValue = Integer.MAX_VALUE;
		int tabuInxedA = -1;
		int tabuIndexB = -1;
		int tabuNewPlaceA = -1;
		int tabuNewPlaceB = -1;

		improved: do {
			do {
				int newPlaceA = this.findBestPlaceForVertex(this.a
						.get(actualIndexA), false, actualIndexB);
				int newPlaceB = this.findBestPlaceForVertex(this.b
						.get(actualIndexB), true, actualIndexA);
				int exchangeValue = this.calculateExchangeValue(actualIndexA,
						newPlaceA, actualIndexB, newPlaceB);
				if (exchangeValue < 0) {
					int vB = this.b.get(actualIndexB);
					int vA = this.a.get(actualIndexA);

					if (this.tabuManager.isTabuVertex(Integer.valueOf(vA))
							|| this.tabuManager.isTabuVertex(Integer
									.valueOf(vB))) {
						if ((tabuA == -1 && tabuB == -1)
								|| (exchangeValue < tabuExchangeValue)) {
							tabuA = vA;
							tabuB = vB;
							tabuExchangeValue = exchangeValue;
							tabuInxedA = actualIndexA;
							tabuIndexB = actualIndexB;
							tabuNewPlaceA = newPlaceA;
							tabuNewPlaceB = newPlaceB;
						}
					} else {
						better = true;

						this.a.remove(actualIndexA);
						this.b.remove(actualIndexB);
						this.a.add(newPlaceB, vB);
						this.b.add(newPlaceA, vA);

						this.tabuManager.add(vA);
						this.tabuManager.add(vB);

						// System.out.println("Exchanged: " + vA + " & " + vB);

						break improved;
					}
				}

				actualIndexB = (actualIndexB + 1) % this.b.size();
			} while (actualIndexB != firstIndexB);
			actualIndexA = (actualIndexA + 1) % this.a.size();
			actualIndexB = firstIndexB;
		} while (actualIndexA != firstIndexA);

		if (!better && (tabuA != -1 && tabuB != -1)) {
			better = true;

			this.a.remove(tabuInxedA);
			this.b.remove(tabuIndexB);
			this.a.add(tabuNewPlaceB, tabuB);
			this.b.add(tabuNewPlaceA, tabuA);

			this.tabuManager.add(tabuA);
			this.tabuManager.add(tabuB);

			// System.out.println("{tabu} Exchanged: " + tabuA + " & " + tabuB);
		}

		return better;
	}

	private int calculateExchangeValue(int oldIndexA, int newIndexA,
			int oldIndexB, int newIndexB) {
		int oldAprev;
		int oldAsucc;
		int oldAprevSucc;
		int newAprev;
		int newAsucc;
		int newAprevSucc;
		int oldBprev;
		int oldBsucc;
		int oldBprevSucc;
		int newBprev;
		int newBsucc;
		int newBprevSucc;

		if (this.a.size() == 1) {
			oldAprev = 0;
			oldAsucc = 0;
			oldAprevSucc = 0;
			newBprev = 0;
			newBsucc = 0;
			newBprevSucc = 0;
		} else {
			int oldIndexAprev = (oldIndexA + this.a.size() - 1) % this.a.size();
			int oldIndexAsucc = (oldIndexA + 1) % this.a.size();
			int newIndexBprev;
			if ((newIndexB + this.a.size() - 1) % this.a.size() != oldIndexA) {
				newIndexBprev = (newIndexB + this.a.size() - 1) % this.a.size();
			} else {
				newIndexBprev = (newIndexB + this.a.size() - 2) % this.a.size();
			}
			int newIndexBsucc;
			if ((newIndexB + 1) % this.a.size() != oldIndexA) {
				newIndexBsucc = (newIndexB + 1) % this.a.size();
			} else {
				newIndexBsucc = (newIndexB + 2) % this.a.size();
			}

			oldAprev = this.vertexes.getDistanceBetween(this.a.get(oldIndexA),
					this.a.get(oldIndexAprev));
			oldAsucc = this.vertexes.getDistanceBetween(this.a.get(oldIndexA),
					this.a.get(oldIndexAsucc));
			oldAprevSucc = this.vertexes.getDistanceBetween(this.a
					.get(oldIndexAprev), this.a.get(oldIndexAsucc));

			newBprev = this.vertexes.getDistanceBetween(this.b.get(oldIndexB),
					this.a.get(newIndexBprev));
			newBsucc = this.vertexes.getDistanceBetween(this.b.get(oldIndexB),
					this.a.get(newIndexBsucc));
			newBprevSucc = this.vertexes.getDistanceBetween(this.a
					.get(newIndexBprev), this.a.get(newIndexBsucc));
		}
		if (this.b.size() == 1) {
			oldBprev = 0;
			oldBsucc = 0;
			oldBprevSucc = 0;
			newAprev = 0;
			newAsucc = 0;
			newAprevSucc = 0;
		} else {
			int oldIndexBprev = (oldIndexB + this.b.size() - 1) % this.b.size();
			int oldIndexBsucc = (oldIndexB + 1) % this.b.size();
			int newIndexAprev;
			if ((newIndexA + this.b.size() - 1) % this.b.size() != oldIndexB) {
				newIndexAprev = (newIndexA + this.b.size() - 1) % this.b.size();
			} else {
				newIndexAprev = (newIndexA + this.b.size() - 2) % this.b.size();
			}
			int newIndexAsucc;
			if ((newIndexA + 1) % this.b.size() != oldIndexB) {
				newIndexAsucc = (newIndexA + 1) % this.b.size();
			} else {
				newIndexAsucc = (newIndexA + 2) % this.b.size();
			}

			oldBprev = this.vertexes.getDistanceBetween(this.b.get(oldIndexB),
					this.b.get(oldIndexBprev));
			oldBsucc = this.vertexes.getDistanceBetween(this.b.get(oldIndexB),
					this.b.get(oldIndexBsucc));
			oldBprevSucc = this.vertexes.getDistanceBetween(this.b
					.get(oldIndexBprev), this.b.get(oldIndexBsucc));

			newAprev = this.vertexes.getDistanceBetween(this.a.get(oldIndexA),
					this.b.get(newIndexAprev));
			newAsucc = this.vertexes.getDistanceBetween(this.a.get(oldIndexA),
					this.b.get(newIndexAsucc));
			newAprevSucc = this.vertexes.getDistanceBetween(this.b
					.get(newIndexAprev), this.b.get(newIndexAsucc));
		}

		int result = (newAprev + newAsucc + oldAprevSucc + newBprev + newBsucc + oldBprevSucc)
				- (oldAprev + oldAsucc + newAprevSucc + oldBprev + oldBsucc + newBprevSucc);
		return result;
	}

	private int findBestPlaceForVertex(int v, boolean inA, int excludeIndex) {
		int resIndex = -1;
		int minChange = Integer.MAX_VALUE;
		List<Integer> list;

		if (inA) {
			list = this.a;
		} else {
			list = this.b;
		}

		int prevIndex;
		int succIndex;
		int diff;

		for (int i = 0; i < list.size(); i++) {
			if (i != excludeIndex) {
				if (i == (excludeIndex + list.size() - 1) % list.size()) {
					prevIndex = (i + list.size() - 1) % list.size();
					succIndex = (excludeIndex + 1) % list.size();
				} else if (i == (excludeIndex + 1) % list.size()) {
					prevIndex = (excludeIndex + list.size() - 1) % list.size();
					succIndex = (i + 1) % list.size();
				} else {
					prevIndex = (i + list.size() - 1) % list.size();
					succIndex = (i + 1) % list.size();
				}

				diff = this.vertexes.getDistanceBetween(i, prevIndex)
						+ this.vertexes.getDistanceBetween(i, succIndex)
						- this.vertexes
								.getDistanceBetween(prevIndex, succIndex);
				if (diff < minChange) {
					minChange = diff;
					resIndex = i;
				}
			}
		}

		if (resIndex == -1) {
			resIndex = 0;
		}

		return resIndex;
	}

	@Override
	public List<Integer> getA() {
		return this.a;
	}

	@Override
	public List<Integer> getB() {
		return this.b;
	}

	@Override
	public boolean hasImproved() {
		return false;
	}
}
